package traverser;

public class PriorityParentQueue {

	PPQNode[] queue;
	int index;  // First empty node
	String lastParent = null;

	public PriorityParentQueue() {
		queue = new PPQNode[512];
		queue[0] = null;
		index = 1;
	}

	// Insert a link into the queue
	public void add(String link, String parent, int priority) {
		queue[index] = new PPQNode(link, parent, priority);
		int iter = index;

		// Float the new value up the queue
		while (iter > 1) {
			if (queue[iter / 2].priority < queue[iter].priority) {
				PPQNode temp = queue[iter / 2];
				queue[iter / 2] = queue[iter];
				queue[iter] = temp;
				iter /= 2;
			} else {
				break;
			}
		}

		index++;

		// Resize the array (if necessary)
		if (index >= queue.length) {
			PPQNode[] temp = new PPQNode[2 * queue.length];
			for (int i = 0; i < queue.length; i++) {
				temp[i] = queue[i];
			}
			queue = temp;
		}
	}

	/*
	// Removes the highest priority entry from the queue, and return the link value
	public String pop() {
		if (queue[1] == null)
			return null;
		lastParent = queue[1].parent;
		String link = queue[1].link;

		// Fix the queue
		int iter = 1;
		while (iter * 2 < index) {
			if (iter * 2 + 1 >= index || queue[iter * 2].priority > queue[iter * 2 + 1].priority) {
				queue[iter] = queue[iter * 2];
				iter = iter * 2;
			} else {
				queue[iter] = queue[iter * 2 + 1];
				iter = iter * 2 + 1;
			}
		}
		
		index--;
		return link;
	}
	*/
	
	
	public String pop() {
		if (queue[1] == null)
			return null;
		lastParent = queue[1].parent;
		String link = queue[1].link;
		
		// Swap the least element with the head
		queue[1] = queue[index-1];
		
		// Percolate the element down to the correct position
		int iter = 1;
		while (iter < index) {			
			int left = iter*2;
			int right = iter*2+1;
			
			// There is no right value
			if (right >= index) {
				// There is no left value
				if (left >= index) {
					break;
				}
				
				// There is a left value, and it's less than iter
				if (queue[left].priority > queue[iter].priority) {
					PPQNode temp = queue[iter];
					queue[iter] = queue[left];
					queue[left] = temp;
					iter = left;
					
				// There is a left value, and it's greater than iter
				} else {
					break;
				}
				
			// There is a right value, but neither of the children are less than iter
			}else if (queue[left].priority <= queue[iter].priority && queue[right].priority <= queue[iter].priority ) {
				break;
				
			// Either the right or the left value is less than iter: swap it.
			} else if (queue[left].priority > queue[right].priority) {
				PPQNode temp = queue[iter];
				queue[iter] = queue[left];
				queue[left] = temp;
				iter = left;
			} else {
				PPQNode temp = queue[iter];
				queue[iter] = queue[right];
				queue[right] = temp;
				iter=right;
			}
		}
		
		index--;
		return link;
	}
	
	public int topPriority () {
		if (queue[1] == null)
			return -1;
		
		return queue[1].priority;
	}

	// Returns the parent (previous search term) of the last link returned by get
	public String lastParent() {
		return lastParent;
	}
	
	// Is there anything left in the queue
	public boolean hasNext() {
		return queue[1] != null;
	}
	
	// Print out the queue in order
	public void print () {
		for (int i = 1; i < index; i *= 2) {
			for (int j = i; j < i*2 && j < index; j++) {
				System.out.print(queue[j].link + " - ");
			}
			System.out.println();
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		PriorityParentQueue test = new PriorityParentQueue();
		for (char i = 'a'; i < 'z'; i++) {
			test.add(Character.toString(i), null, (int)i);
			
		}
		
		test.print();
		for (int i = 0; i < 10; i++) {
			System.out.println(test.pop());
			System.out.println("Top pri: " + (char)test.topPriority());
			test.print();
		}
		
	}

	class PPQNode {
		public String link;
		public String parent;
		public int priority;

		public PPQNode(String link, String parent, int priority) {
			this.link = link;
			this.parent = parent;
			this.priority = priority;
		}
	}

}
